Search Results

Documents authored by Wijsen, Jef

Document
DOI: 10.4230/LIPIcs.ICDT.2023.23
Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting

Authors: Aziz Amezian El Khalfioui and Jef Wijsen

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
The problem of consistent query answering for primary keys and self-join-free conjunctive queries has been intensively studied in recent years and is by now well understood. In this paper, we study an extension of this problem with counting. The queries we consider count how many times each value occurs in a designated (possibly composite) column of an answer to a full conjunctive query. In a setting of database repairs, we adopt the semantics of [Arenas et al., ICDT 2001] which computes tight lower and upper bounds on these counts, where the bounds are taken over all repairs. Ariel Fuxman defined in his PhD thesis a syntactic class of queries, called Cforest, for which this computation can be done by executing two first-order queries (one for lower bounds, and one for upper bounds) followed by simple counting steps. We use the term "parsimonious counting" for this computation. A natural question is whether Cforest contains all self-join-free conjunctive queries that admit parsimonious counting. We answer this question negatively. We define a new syntactic class of queries, called Cparsimony, and prove that it contains all (and only) self-join-free conjunctive queries that admit parsimonious counting.
Cite as

Aziz Amezian El Khalfioui and Jef Wijsen. Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amezianelkhalfioui_et_al:LIPIcs.ICDT.2023.23,
  author =	{Amezian El Khalfioui, Aziz and Wijsen, Jef},
  title =	{{Consistent Query Answering for Primary Keys and Conjunctive Queries with Counting}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.23},
  URN =		{urn:nbn:de:0030-drops-177659},
  doi =		{10.4230/LIPIcs.ICDT.2023.23},
  annote =	{Keywords: Consistent query answering, primary key, conjunctive query, aggregation, counting}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.23
Consistent Query Answering for Primary Keys in Logspace

Authors: Paraschos Koutris and Jef Wijsen

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [Koutris and Wijsen, ACM TODS, 2017], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.
Cite as

Paraschos Koutris and Jef Wijsen. Consistent Query Answering for Primary Keys in Logspace. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{koutris_et_al:LIPIcs.ICDT.2019.23,
  author =	{Koutris, Paraschos and Wijsen, Jef},
  title =	{{Consistent Query Answering for Primary Keys in Logspace}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.23},
  URN =		{urn:nbn:de:0030-drops-103252},
  doi =		{10.4230/LIPIcs.ICDT.2019.23},
  annote =	{Keywords: conjunctive queries, consistent query answering, Datalog, primary keys}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TIME.2017
LIPIcs, Volume 90, TIME'17, Complete Volume

Authors: Sven Schewe, Thomas Schneider, and Jef Wijsen

Published in: LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)

Abstract
LIPIcs, Volume 90, TIME'17, Complete Volume
Cite as

24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{schewe_et_al:LIPIcs.TIME.2017,
  title =	{{LIPIcs, Volume 90, TIME'17, Complete Volume}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Schewe, Sven and Schneider, Thomas and Wijsen, Jef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017},
  URN =		{urn:nbn:de:0030-drops-80233},
  doi =		{10.4230/LIPIcs.TIME.2017},
  annote =	{Keywords: Distributed Systems, Design Tools and Techniques, Software/Program Verification, Security and Protection, Models of Computation, Specifying and Verifying and Reasoning about Programs, Mathematical Logic, \lbrackNumerical Linear Algebra\rbrack Linear Systems, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TIME.2017.0
Front Matter, Table of Contents, Preface, Organization, List of Authors

Authors: Sven Schewe, Thomas Schneider, and Jef Wijsen

Published in: LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017)

Abstract
Front Matter, Table of Contents, Preface, Organization, List of Authors
Cite as

24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schewe_et_al:LIPIcs.TIME.2017.0,
  author =	{Schewe, Sven and Schneider, Thomas and Wijsen, Jef},
  title =	{{Front Matter, Table of Contents, Preface, Organization, List of Authors}},
  booktitle =	{24th International Symposium on Temporal Representation and Reasoning (TIME 2017)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-052-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{90},
  editor =	{Schewe, Sven and Schneider, Thomas and Wijsen, Jef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.0},
  URN =		{urn:nbn:de:0030-drops-79117},
  doi =		{10.4230/LIPIcs.TIME.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Organization, List of Authors}
}
Document
DOI: 10.4230/DagSemProc.08421.5
08421 Working Group: Imprecision, Diversity and Uncertainty: Disentangling Threads in Uncertainty Management

Authors: Myra Spiliopoulou, Maurice van Keulen, Hans-Joachim Lenz, Jef Wijsen, Matthias Renz, Rudolf Kruse, and Mirco Stern

Published in: Dagstuhl Seminar Proceedings, Volume 8421, Uncertainty Management in Information Systems (2009)

Abstract
We report on the results of Workgroup 1 on "Imprecision, Diversity and Uncertainty". We set the scene by elaborating on where uncertainty comes from and what the ground truth is. In real world applications, the data observed may not be as expected: they may violate constraints, or, more generally, disagree with the anticipated model of the world. This leads to two orthogonal cases: The data may be erroneous, i.e. they must be corrected. Or, the model may outdated and must be adjusted to the data. After elaborating on this fundamental distinction, we address the issues of measuring uncertainty and exploiting uncertainty in real applications. We conclude with a list of challenges that should be addressed when dealing with uncertainty.
Cite as

Myra Spiliopoulou, Maurice van Keulen, Hans-Joachim Lenz, Jef Wijsen, Matthias Renz, Rudolf Kruse, and Mirco Stern. 08421 Working Group: Imprecision, Diversity and Uncertainty: Disentangling Threads in Uncertainty Management. In Uncertainty Management in Information Systems. Dagstuhl Seminar Proceedings, Volume 8421, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{spiliopoulou_et_al:DagSemProc.08421.5,
  author =	{Spiliopoulou, Myra and van Keulen, Maurice and Lenz, Hans-Joachim and Wijsen, Jef and Renz, Matthias and Kruse, Rudolf and Stern, Mirco},
  title =	{{08421 Working Group: Imprecision, Diversity and Uncertainty: Disentangling Threads in Uncertainty Management}},
  booktitle =	{Uncertainty Management in Information Systems},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8421},
  editor =	{Christoph Koch and Birgitta K\"{o}nig-Ries and Volker Markl and Maurice van Keulen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08421.5},
  URN =		{urn:nbn:de:0030-drops-19375},
  doi =		{10.4230/DagSemProc.08421.5},
  annote =	{Keywords: Uncertainty of data, uncertainty of models, measuring uncertainty, propagating uncertainty, challenges of dealing with uncertainty}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact